package pro.softzhang.algo.abc;


import pro.softzhang.algo.flag.knowledge.KBinarySearch;

/**
 * 标准查找算法
 */
public class Search {
    public static void main(String[] args) {
        int[] nums = {-1,0,3,5,9,12};
        int target = 9;
        System.out.println(new BinarySearch().search1(nums, target));
    }

    /**
     * 顺序查找
     */
    static
    class SequentialSearch {
        public static int sequentialSearch(int[] arr, int k) {
            int idx = arr.length - 1;
            while(idx >= 0 && arr[idx] != k)
                idx--;
            return idx;
        }
    }

    /**
     * 二分查找
     * @return
     */
    @KBinarySearch
    static
    class BinarySearch {
        /**
         * 模板1 标准模板
         * @param nums
         * @param target
         * @return
         */
        public int search1(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] > target) {
                    right = mid - 1;
                } else if (nums[mid] < target){
                    left = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }

        /**
         * 模板2
         * @param nums
         * @param target
         * @return
         */
        public int search2(int[] nums, int target){
            if(nums == null || nums.length == 0)
                return -1;

            int left = 0, right = nums.length;
            while(left < right){
                // Prevent (left + right) overflow
                int mid = left + (right - left) / 2;
                if(nums[mid] == target){
                    return mid;
                }
                else if(nums[mid] < target) {
                    left = mid + 1;
                }
                else {
                    right = mid;
                }
            }

            // Post-processing:
            // End Condition: left == right
            if(left != nums.length && nums[left] == target) {
                return left;
            }
            return -1;
        }

        /**
         * 非递归折半查找
         * @param arr
         * @param k
         * @return
         */
        public static int nonRecursiveBinarySearch(int[] arr, int k) {
            // 0. 定义左右指针
            int leftPointer = 0, rightPointer = arr.length - 1;
            // 1. 进行查找
            while(leftPointer <= rightPointer) {
                // 1.0. 定义中间
                int middleIdx = (leftPointer + rightPointer) / 2;
                // 1.1. 进行比较
                if(k < arr[middleIdx]) // 在左边
                    rightPointer = middleIdx - 1;
                else if(k > arr[middleIdx]) // 在右边
                    leftPointer = middleIdx + 1;
                else
                    return middleIdx;
            }
            // 2. 没找到
            return -1;
        }

        /**
         * 递归折半查找
         * @param arr
         * @param k
         * @param left
         * @param right
         * @return
         */
        public static int recursiveBinarySearch(int[] arr, int k, int left, int right) {
            // 0. 是否进行查找
            if(left <= right) {
                // 0.0. 明确中心点
                int middle = (left + right) / 2;
                // 0.1. 在左方
                if(k < arr[middle]) return recursiveBinarySearch(arr, k, left, middle - 1);
                    // 0.2. 在右方
                else if(k > arr[middle]) return recursiveBinarySearch(arr, k, middle +1, right);
                    // 0.3. 相等
                else return middle;
            }
            // 1. 没找到
            return -1;
        }
    }
}
